package com.acwing.partition9;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/12/1 12:43
 */
public class AC854Floyd求最短路 {

    private static final int INF = 0x3F3F3F3F;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]), k = Integer.parseInt(s[2]);
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split(" ");
            int a = Integer.parseInt(s[0]), b = Integer.parseInt(s[1]), c = Integer.parseInt(s[2]);
            edges[i][0] = a;
            edges[i][1] = b;
            edges[i][2] = c;
        }
        int[][] dp = floyd(n, edges);
        while (k-- > 0) {
            s = reader.readLine().split(" ");
            n = Integer.parseInt(s[0]);
            m = Integer.parseInt(s[1]);
            if (dp[n][m] > INF / 2) writer.write("impossible\n");
            else writer.write(dp[n][m] + "\n");
            writer.flush();
        }
    }

    private static int[][] floyd(int n, int[][] edges) {
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) dp[i][j] = i == j ? 0 : INF;
        }
        for (int[] edge : edges) dp[edge[0]][edge[1]] = Math.min(dp[edge[0]][edge[1]], edge[2]);
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp;
    }
}
